#include"personTree.h"  

using namespace std;

Person::Person(int identity, string name, string sex)
{
    m_identity = identity;
    m_name = name;
    m_sex = sex;
}

Employee::Employee(int identity, string name, string sex, string dept):Person(identity, name, sex), m_dept(dept){}
void Employee::Display()
{
    cout << " 证件号:" << m_identity << " 姓名:" << m_name << " 性别:" << m_sex << " 部门:" << m_dept << endl;
}

Teacher::Teacher(int identity, string name, string sex, string subject):Person(identity, name, sex), m_subject(subject){}
void Teacher::Display()
{
    cout << " 证件号:" << m_identity << " 姓名:" << m_name << " 性别:" << m_sex << " 科目:" << m_subject << endl;
}

Student::Student(int identity, string name, string sex, int grade):Person(identity, name, sex), m_grade(grade){}
void Student::Display()
{
    cout << " 证件号:" << m_identity << " 姓名:" << m_name << " 性别:" << m_sex << " 年级:" << m_grade << endl;
}

TreeNode::TreeNode(Person *data):m_data(data), lChild(NULL), rChild(NULL){}

PersonTree::PersonTree():m_root(NULL){}
PersonTree::~PersonTree()
{
    Release(m_root);
}
TreeNode* PersonTree::GetRoot()
{
    return m_root;
}
void PersonTree::InsertTree(Person *data)
{
    if (!this->m_root)
    {
        this->m_root = new TreeNode(data);
    } else {
        this->InsertTree(this->m_root, data);
    }
}
TreeNode* PersonTree::InsertTree(TreeNode *node, Person *data)
{
    if (node == NULL) {
        node = new TreeNode(data);
    }
    else {
        if (data->m_identity < node->m_data->m_identity) {
            node->lChild = InsertTree(node->lChild, data);
        }
        else {
            node->rChild = InsertTree(node->rChild, data);
        }
    }
    return node;
}
void PersonTree::InOder(TreeNode* node)
{
    if (node == NULL) {
        return;
    }
    else {
        InOder(node->lChild);
        node->m_data->Display();
        InOder(node->rChild);
    }
}
void PersonTree::Find(int identity)
{
    TreeNode *node = this->m_root;
    while (node) {
        if (identity < node->m_data->m_identity) {
            node = node->lChild;
        }
        else if (identity == node->m_data->m_identity) {
            node->m_data->Display();
            return;
        }
        else {
            node = node->rChild;
        }
    }
    cout << "没有找到" << endl;
    return;
}
void PersonTree::Delete(int identity)
{
    TreeNode *node = this->m_root;
    // 记录node父节点
    TreeNode *pre = this->m_root;
    // 检查二叉排序树中key所在的节点
    while (node) {
        if (identity < node->m_data->m_identity) {
            pre = node;
            node = node->lChild;
        }
        else if (identity == node->m_data->m_identity) {
            // 叶子节点直接删除
            if ( !node->lChild && !node->rChild) {
               // 是根节点直接置为空
               if (node == this->m_root) {
                   this->m_root = NULL;
               }
               // 叶子节点释放
               else {
                   if (node == pre->lChild) {
                       pre->lChild = NULL;
                   }
                   else {
                       pre->rChild = NULL;
                   }
                   delete node;
               }
            }
            // 左子树为空重接右子树
            else if (!node->lChild) {
                if (node == this->m_root) {
                    this->m_root = node->rChild;
                }
                else {
                    if (pre->lChild == node) {
                        pre->lChild = node->rChild;
                    }
                    else {
                        pre->rChild = node->rChild;
                    }
                }
                delete node;
            }
            // 右子树为空重接左子树
            else if (!node->rChild) {
                if (node == this->m_root) {
                    this->m_root = node->lChild;
                }
                else {
                    if (pre->lChild == node) {
                        pre->lChild = node->lChild;
                    }
                    else {
                        pre->rChild = node->lChild;
                    }
                }
                delete node;
            }
            // 左右子树均不为空
            else {
                TreeNode *node1, *node2;
                node1 = node;
                node2 = node->lChild;
                // 找到待删节点前驱节点代替当前节点，方法:左转到最右节点
                while (node2->rChild) {
                    node1 = node2;
                    node2 = node2->rChild;
                }
                node->m_data = node2->m_data;
                // 判断是否执行while循环
                // 如果执行了while，则重接待删除节点前驱节点node2的左子树
                if (node1 != node) {
                    node1->rChild = node2->lChild;
                }
                // 如果没有执行while，则直接续接左子树
                else {
                    node1->lChild = node2->lChild;
                }
                delete node2;
            }
            return;
        }
        else {
            pre = node;
            node = node->rChild;
        }
    }
    cout << "未找到该节点" << endl;
    return;
}
void PersonTree::Release(TreeNode* root)
{
    if (root != NULL) {
        Release(root->lChild);
        Release(root->rChild);
        delete root;
    }
}
